In many multiprocessor systems, all of the processors access a common memory, referred to as main memory. Typically, main memory is not capable of supplying data and instructions to multiple processors at adequate speeds. To compensate for the speed deficiencies of main memory, caches are usually incorporated. Caches are small high-speed memories located between main memory and a processor, and that are updated to contain memory data that was recently requested by the processor. The processor can generally obtain a copy of memory data much more quickly from its cache than from the main memory.
In multiprocessor systems, multiple copies of a particular data item may reside within multiple caches at any given time. Because of this, a memory coherency protocol must be used to ensure that all processors within the system operate from the same, most recent, copy of the memory data. This type of protocol allows data to be shared among many devices for read-only purposes. Before a device can modify the data, it must gain exclusive access to the data. In this case, all other cached copies of the data are marked as unusable, or “invalidated”. After a device gains exclusive access to data, the device may, but is not required to, modify the data. When a device relinquishes exclusive access rights, any updated copy of the data must be stored back to the main memory, or provided to another cache within the system.
To implement a cache coherency protocol, some mechanism must be used to record the location and state of each cacheable unit of memory data. One mechanism for performing this type of data tracking involves use of a snoop filter. A snoop filter is a cache that is used to record the location of each copy of a unit of data that exists outside of the main memory. A record is created within the snoop filter as the copy is made, and is removed from the snoop filter when the copy is returned to the main memory. A snoop filter is generally large enough to contain entries for a subset of all units of data residing in the main memory. It does not include enough memory space to track every data unit at once.
One problem with snoop filters is that they are generally implemented as set addressable caches. As is known in the art, a set addressable cache can only store a limited number of blocks for a given set address. If all entries within a set address store valid blocks, data must be aged from the cache. When entries are aged from a snoop filter, however, the data unit that is tracked by that entry must be aged from cache back to main memory. This may severely impact system performance.
One way to address the problem associated with snoop filters is to use a memory directory. A memory directory provides a respective entry for each data unit that is stored within main memory. Thus, a memory directory tracks the location of even those data units that only reside within the main memory. A memory directory is therefore likely to be much larger than a snoop filter, and will generally require longer access time. This may slow processing throughput.
What is needed, therefore, is an improved system and method for implementing a coherency protocol in a multiprocessor system.